/***
 * 求x的n次方
*/

#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

// O(n) for循环求结果
int func1(int x, int n) {
    int result = 1; // 任何数的0次方等于1
    for (int i = 0; i < n; i++) {
        result *= x;
    }

    return result;
}

// 递归 下面代码复杂度是多少呢？
// 本质：递归次数 * 每次递归中的操作次数
// 故下面代码时间复杂度是 O(n)
int func2(int x, int n) {
    if (n == 0) {
        return 1; // 任何数的0次方等于1
    }
    return func2(x, n - 1) * x;
}

// 还是递归
// 时间复杂度还是O(n)
// 满二叉树性质 m为深度 总节点数：2 ^ (m + 1) - 1
int func3(int x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }

    if (n % 2 == 0) {
        return func3(x, n / 2) * func3(x, n / 2);
    }
    return func3(x, n / 2) * func3(x, n / 2) * x;
}

/**
 * 下面仅仅有一个递归调用，且每次都是n/2，
 * 所以这里一共调用了log以2为底n的对数次。
 * 时间复杂度为O(logn)
*/
int func4(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;

    int result = func4(x, n / 2);
    if (n % 2 == 0) {
        return result * result;
    }
    return result * result * x;
}

int main() {
    int x, n;

    while (1) {
        cout << "cin x: " << endl;
        cin >> x;
        cout << "cin n: " << endl;
        cin >> n;

        auto startTime = high_resolution_clock::now();
        int result = func4(x, n);
        auto endTime = high_resolution_clock::now();

        auto duration = duration_cast<milliseconds>(endTime - startTime);
            
        cout << "cost time: " << duration.count() << " ms" << endl;

        cout << x << " ^ " << n << " = " << result << endl;
    }
    
    system("pause");
    return 0;
}